import java.util.PriorityQueue;
import java.util.Comparator;

/**
 * 包含了“合并 K 个有序链表”问题的解决方案。
 * 核心方法是使用优先级队列（最小堆）来实现高效的 K 路归并。
 */
public class Solution23 {

    /**
     * 定义了单向链表的节点结构。
     * 作为公共静态内部类，方便外部直接访问和使用。
     */
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 将一个包含 K 个有序链表的数组，合并成一个单一的、全局有序的链表。
     *
     * @param lists 包含 K 个有序链表的数组。
     * @return 合并后新链表的头节点。
     */
    public ListNode mergeKLists(ListNode[] lists) {
        // 处理边界情况：如果输入的数组为空或长度为0，直接返回null。
        if (lists == null || lists.length == 0) {
            return null;
        }

        // 创建一个虚拟头节点（哨兵节点），用于简化链表构建过程。
        ListNode dummyHead = new ListNode(0);
        // 创建一个移动指针，负责在新链表的末尾进行连接操作。
        ListNode current = dummyHead;

        // 初始化一个优先级队列（内部为最小堆）。
        // 它的作用是在 K 个链表的头节点中，快速找到值最小的那个节点。
        // 我们通过自定义比较器 (a, b) -> a.val - b.val 来实现按节点值升序排列（小顶堆）。
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));

        // 将所有 K 个链表的非空头节点加入到优先级队列中。
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }

        // 当优先级队列不为空时，循环执行以下操作。
        while (!pq.isEmpty()) {
            // 从队列中取出当前所有“候选”节点中值最小的那个节点。
            ListNode minNode = pq.poll();

            // 将这个最小节点连接到结果链表的末尾。
            current.next = minNode;

            // 如果这个最小节点后面还有节点，则将其下一个节点加入队列，成为新的“候选人”。
            if (minNode.next != null) {
                pq.add(minNode.next);
            }

            // 移动结果链表的构造指针，为连接下一个节点做准备。
            current = current.next;
        }

        // 返回虚拟头节点的下一个节点，即新链表的真正头节点。
        return dummyHead.next;
    }
}